package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 1312. 让字符串成为回文串的最少插入次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/16 11:35
 */
public class MinInsertions {


    public static void main(String[] args) {
        MinInsertions test = new MinInsertions();

        // 0
//        String str = "aazaa";

        // 2
//        String str = "mbadm";

        // 5
//        String str = "leetcode";

        // 33
//        String str = "mxaosaoifhjtepsbjkqcfypinkmutwyoijlqcbngyeezjdfawm";

        // 1
//        String str = "abb";

        // 9
//        String str = "ccewnxhytsr";

        String str = Utils.getStr(10, 'a', 'z');

        int i = test.minInsertions(str);

        System.out.println(i);
    }


    private char[] chars;
    private int end2;

    public int minInsertions(String s) {
        int length = s.length();
        if (length == 1) {
            return 0;
        }
        if (length == 2) {
            return s.charAt(0) == s.charAt(1) ? 0 : 1;
        }
        this.chars = s.toCharArray();
        this.end2 = length - 1;
        int max = length  - (find(0, 1) << 1);
        for (int i = 1; i < length - 1; i++) {
            int a = find(i - 1, i + 1);
            max = Math.min(max, length - 1 - (a << 1));
            int b = find( i, i + 1);
            max = Math.min(max, length - (b << 1));
        }
        return max;
    }

    private int find( int end1, int st2) {
        int m = end1 + 1;
        int n = end2 - st2 + 1;
        int[][] arr = new int[m][n];
        for (int i = end1; i >= 0; i--) {
            for (int j = st2; j <= end2; j++) {
                int v = 0;
                if (i + 1 <= end1 && j - 1 >= st2) {
                    v = arr[end1 - i - 1][j - st2 - 1];
                }
                if (chars[i] == chars[j]) {
                    arr[end1 - i][j - st2] = v + 1;
                } else {
                    if (i + 1 <= end1) {
                        v = Math.max(v, arr[end1 - i - 1][j - st2]);
                    }
                    if (j - 1 >= st2) {
                        v = Math.max(v, arr[end1 - i][j - st2 - 1]);
                    }
                    arr[end1 - i][j - st2] = v;
                }
            }
        }
        return arr[m - 1][n - 1];
    }

}
